699. Falling Squares.go

package leetcode

import (
"sort"

"github.com/halfrost/LeetCode-Go/template"
)

funcfallingSquares(positions [][]int) []int {
st, ans, posMap, maxHeight:= template.SegmentTree{}, make([]int, 0, len(positions)), discretization(positions), 0
tmp:=make([]int, len(posMap))
st.Init(tmp, func(i, jint) int {
returnmax(i, j)
 })
for_, p:=rangepositions {
h:=st.QueryLazy(posMap[p[0]], posMap[p[0]+p[1]-1]) +p[1]
st.UpdateLazy(posMap[p[0]], posMap[p[0]+p[1]-1], h)
maxHeight=max(maxHeight, h)
ans=append(ans, maxHeight)
 }
returnans
}

funcdiscretization(positions [][]int) map[int]int {
tmpMap, posArray, posMap:=map[int]int{}, []int{}, map[int]int{}
for_, pos:=rangepositions {
tmpMap[pos[0]]++
tmpMap[pos[0]+pos[1]-1]++
 }
fork:=rangetmpMap {
posArray=append(posArray, k)
 }
sort.Ints(posArray)
fori, pos:=rangeposArray {
posMap[pos] =i
 }
returnposMap
}

funcmax(aint, bint) int {
ifa>b {
returna
 }
returnb
}